package com.mgq.algorithm.twotree;

/**
 * @author MaGuangQi
 * 删除BST中节点
 * @date 2022-02-25 16:57
 **/
public class DeleteNodeAVL_450 {

    TreeNode deleteNode(TreeNode root, int key) {
        //删除节点
        if(root==null) return null;
        //找到节点
        if (root.val == key) {
            //删除节点,分为3种情况
            //情况一 删除的node没有左子树和右子树
            //直接删除
            if(root.left==null&&root.right==null) return null;
            //情况二: 有一个节点,让这个孩子接替自己的位置。
            if(root.left==null) return root.right;
            if(root.right==null) return root.left;
            //情况三: 有2个节点.有2种办法,找到左树的最大值或者右树的最小值,然后用这个值替换当前节点
            //此处使用 右树的最小值
            TreeNode minNode = getMin(root);
            //修改值
            root.val=minNode.val;
            //把minNode删掉,返回结果是根,因为删的是root的right,所以把结果给root.right
            root.right=deleteNode(root.right, minNode.val);
        } else if (root.val < key) {
            root.right = deleteNode(root.right, key);
        } else {
            root.left = deleteNode(root.left, key);
        }
        return root;
    }

    TreeNode getMin(TreeNode root) {
        //BST最左节点就是最小节点
        while (root.left!=null){
            root=root.left;
        }
        return root;
    }
    //模板
    public void BST(TreeNode root,int target){
        if(root==null) return;
        if (root.val == target) {
            //找到节点.执行其他操作
        }
        if (root.val > target) {
            BST(root.left,target);
        }
        if (root.val < target) {
            BST(root.right,target);
        }
    }
}

